package com.ww.springboot.boot.algorithm.leetcode1;

import java.util.*;

/**
 * 描述：
 * <p>
 * https://leetcode-cn.com/problems/combination-sum/
 * <p>
 * 其实就是将值拆分不断拆分 再在数组中查找拆分后的值是否有符合条件的组合
 *
 * @author 🧑 ‍wanwei
 * @since 2022-03-09 15:59
 */
public class AC39 {


    public static void main(String[] args) {
        int[] candidates = {2, 3, 5};
        System.out.println(combinationSum(candidates, 8));
    }

    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        Map<Integer, Set<List<Integer>>> map = new HashMap<>();
        //找到比target小的数
        Set<List<Integer>> lists = combinationSum2(candidates, target, map);
        List<List<Integer>> list = new ArrayList<>();
        list.addAll(lists);
        return list;
    }

    //动态规划 怎么解决元素重复问题？  --回溯 本身就不用考虑回溯的问题
    public static Set<List<Integer>> combinationSum2(int[] candidates, int target, Map<Integer, Set<List<Integer>>> map) {
        Set<List<Integer>> mapData = map.get(target);
        if (mapData != null) {
            return mapData;
        }
        Set<List<Integer>> lists = new HashSet<>();
        if (target == 0) {
            return new HashSet<>();
        }
        //去除重复数据
        List<Integer> list2 = new ArrayList<>();
        for (int i = 0; i < candidates.length; i++) {
            int num = candidates[i];
            if (target == num) {
                List<Integer> list = new ArrayList<>();
                list.add(target);
                lists.add(list);
            } else if (target > num) {
                if (list2.contains(num) || list2.contains(target - num)) {
                    continue;
                }
                list2.add(num);
                list2.add(target - num);
                Set<List<Integer>> lists1 = combinationSum2(candidates, num, map);
                Set<List<Integer>> lists2 = combinationSum2(candidates, target - num, map);
                if (lists1.size() == 0 || lists2.size() == 0) {
                    continue;
                }
                for (Iterator<List<Integer>> iterator = lists1.iterator(); iterator.hasNext();) {
                    List<Integer> listA = iterator.next();
                    for (Iterator<List<Integer>> iterator2 = lists2.iterator(); iterator2.hasNext(); ) {
                        List<Integer> list = new ArrayList<>();
                        List<Integer> listB = iterator2.next();
                        list.addAll(listA);
                        list.addAll(listB);
                        Collections.sort(list);
                        lists.add(list);
                    }
                }
            }
        }
        map.put(target, lists);
        return lists;
    }

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Map<Integer, Set<List<Integer>>> map = new HashMap<>();
        //对candidates数组进行排序
        Arrays.sort(candidates);
        int len = candidates.length;
        for (int i = 1; i <= target; i++) {
            //初始化map
            map.put(i, new HashSet<>());
            //对candidates数组进行循环
            for (int j = 0; j < len && candidates[j] <= target; j++) {
                if (i == candidates[j]) {
                    //相等即为相减为0的情况，直接加入set集合即可
                    List<Integer> temp = new ArrayList<>();
                    temp.add(i);
                    map.get(i).add(temp);
                } else if (i > candidates[j]) {
                    //i-candidates[j]是map的key
                    int key = i - candidates[j];
                    //使用迭代器对对应key的set集合进行遍历
                    //如果candidates数组不包含这个key值，对应的set集合会为空，故这里不需要做单独判断
                    for (Iterator iterator = map.get(key).iterator(); iterator.hasNext(); ) {
                        List list = (List) iterator.next();
                        //set集合里面的每一个list都要加入candidates[j]，然后放入到以i为key的集合中
                        List tempList = new ArrayList<>();
                        tempList.addAll(list);
                        tempList.add(candidates[j]);
                        //排序是为了通过set集合去重
                        Collections.sort(tempList);
                        map.get(i).add(tempList);
                    }
                }
            }
        }
        result.addAll(map.get(target));
        return result;
    }
}
